package com.hy.trie;

/**
 * Created With IntelliJ IDEA.
 * Descriptions:
 * author: Mr.Du
 * Date: 2023/10/12
 * Time: 16:40
 */
public class WordDictionary {

    WordDictionary[] child = new WordDictionary[26];
    boolean isEnd = false;
    public WordDictionary() {

    }

    public void addWord(String word) {
        WordDictionary p = this;
        for(int i = 0;i < word.length();i++){
            int index = word.charAt(i) - 'a';
            if(p.child[index] == null){
                p.child[index] = new WordDictionary();
            }
            p = p.child[index];
        }
        p.isEnd = true;
    }

    public boolean search(String word) {
        WordDictionary p = this;
        return searchPre(word, 0, p);
    }

    public boolean searchPre(String word, int start, WordDictionary p){
        if(start == word.length()){
            return p.isEnd;
        }
        char cc = word.charAt(start);
        if(cc != '.'){
            int c = cc - 'a';
            if(p.child[c] == null){
                return false;
            }
            p = p.child[c];
            return searchPre(word, start + 1, p);
        }else{
            for(int i = 0;i < p.child.length;i++){
                WordDictionary tmp = p.child[i];
                if(tmp != null) {
                    if (searchPre(word, start + 1, tmp)) {
                        return true; // 如果有一个子节点返回 true，就可以停止搜索
                    }
                }
            }
            return false;
        }
    }

    public static void main(String[] args) {
        WordDictionary wordDictionary = new WordDictionary();
        wordDictionary.addWord("a");
        wordDictionary.addWord("a");
        wordDictionary.search(".");  //true
        wordDictionary.search("a");  //true
        wordDictionary.search("aa");  //false  true
        wordDictionary.search("a");  //true
        wordDictionary.search(".a");  //false
        wordDictionary.search("a.");  //false  true
    }
}
